package com.lx.algorithm.LinkedList;

/**
 * Description: 多指针链表练习
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-20 21:28:22
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-20     张李鑫                     1.0         1.0 Version
 */
public class SpecialNode {
    static class Node {
        int val;
        Node next;
        Node random;

        Node(int val) {
            val = val;
        }
    }
//    public static Node copyRandomList2(Node head) {
//        if (head == null) {
//            return null;
//        }
//        Node cur = head;
//        Node next = null;
//        // 1 -> 2 -> 3 -> null
//        // 1 -> 1' -> 2 -> 2' -> 3 -> 3'
//        while (cur != null) {
//            next = cur.next;
//            cur.next = new Node(cur.value);
//            cur.next.next = next;
//            cur = next;
//        }
//        cur = head;
//        Node copy = null;
//        // 1 1' 2 2' 3 3'
//        // 依次设置 1' 2' 3' random指针
//        while (cur != null) {
//            next = cur.next.next;
//            copy = cur.next;
//            copy.rand = cur.rand != null ? cur.rand.next : null;
//            cur = next;
//        }
//        Node res = head.next;
//        cur = head;
//        // 老 新 混在一起，next方向上，random正确
//        // next方向上，把新老链表分离
//        while (cur != null) {
//            next = cur.next.next;
//            copy = cur.next;
//            cur.next = next;
//            copy.next = next != null ? next.next : null;
//            cur = next;
//        }
//        return res;
//    }

    /**
     * rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。
     * 给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
     * 【要求】
     * 时间复杂度O(N)，额外空间复杂度O(1)
     * <p>
     * <p>
     * 实现思路 先遍历一遍 复制一个节点拼接在原节点的后面
     * 然后后续再次遍历 每次步长为2
     * 然后恢复链表
     */

    public static Node specialNode(Node node) {
        if (node == null || node.next == null) {
            return node;
        }
        Node head = node;
        Node nextNode = null;
        //复制一个拷贝节点拼接在原节点后面
        while (head != null) {
            nextNode = head.next;
            Node copyNode = new Node(head.val);
            head.next = copyNode;
            copyNode.next = nextNode;
            head = nextNode;
        }
        head = node;
        Node rand = null;
        //步长为2去遍历 把rand指针赋予copyNode
        while (head != null) {
            nextNode = head.next;
            rand = head.random;
            //上面这种写法如果rand是null next肯定也是null就会空指针 所以 先判断当前节点的rand是不是null 如果不是 在rand.next
//            nextNode.rand = rand.next==null?null:rand.next;
            nextNode.random = head.random==null?null:head.random.next;
            head = nextNode.next;
        }
        Node copyNode = node.next;
        Node next=null;
        Node copy=null;
//        Node oldNode=null;
        head = node;
        while (head != null) {
            copy=head.next;
            next=head.next.next;
            head.next=next;
            copy.next=next==null?null:next.next;
            head=next;
        }

        return copyNode;
    }





    public static void main(String[] args) {
        Node node = new Node(5);
        Node node1 = new Node(51);
        Node node2 = new Node(53);
        Node node3 = new Node(54);
        Node node4 = new Node(55);
        Node node5 = new Node(56);
        Node node6 = new Node(57);
        Node node7 = new Node(58);

        node.next=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=node7;


        node.random=node5;
        node5.random=node1;



        Node node8 = specialNode(node);
        System.out.println(123);
    }

}